1. Field of the Invention
Implementations consistent with principles of the invention relate generally to data lookup, and more particularly, to data lookup using linked lists.
2. Description of Related Art
A hashed linked list is a widely used data structure for databases with long access keys. A hash function may be applied to each long access key, resulting in a hash result having a shorter length than the input key. Unfortunately, efficiently implemented hash functions may enable multiple input keys to map to an identical hash result. These hash collisions may be handled by linking related key data together in a linked list. A lookup into such a database typically requires a recursive search into the hashed linked list. Each phase of the recursive search requires a matching comparison of a key with data in the linked list. Such a process requires multiple accesses to external memories and multiple compare instructions.